package _18_剑指OfferII;

import _18_剑指OfferII.datastrcute.TreeNode;

import java.util.LinkedList;
import java.util.Queue;

public class _045_剑指OfferII二叉树最底层最左边的值 {

    private int deep;

    private int res;

    // 深度遍历
    public int findBottomLeftValue(TreeNode root) {

        dfs(1, root);
        return res;
    }

    private void dfs(int deep, TreeNode root) {
        if (root == null) return;

        if (deep > this.deep) {
            this.deep = deep;
            this.res = root.val;
        }

        dfs(deep + 1, root.left);
        dfs(deep + 1, root.right);
    }

    // 层序遍历
    public int findBottomLeftValue1(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);

        int first = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            first = queue.peek().val;
            while (size-- > 0) {
                TreeNode node = queue.poll();
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
        }
        return first;
    }

}
